#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    ListNode* swapPairs(ListNode* head)
    {
        if (!head || !head->next) return head;
        ListNode* cur = head, * next = cur->next;
        ListNode* tmp = swapPairs(head->next->next);
        next->next = cur;
        cur->next = tmp;
        return next;
    }
};
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        ListNode* p1 = head, * p2 = head;
        while (n--) p2 = p2->next;

        if (p2 == nullptr)
        {
            ListNode* ret = head->next;
            delete head;
            return ret;
        }

        ListNode* prev = nullptr;
        while (p2)
        {
            prev = p1;
            p1 = p1->next;
            p2 = p2->next;
        }

        ListNode* next = p1->next;
        prev->next = next;
        delete p1;

        return head;
    }
};
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
    {
        ListNode* newhead = new ListNode;
        ListNode* newtail = newhead;
        ListNode* cur1 = l1, * cur2 = l2;
        int sum = 0;
        while (cur1 || cur2 || sum)
        {
            if (cur1)
            {
                sum += cur1->val;
                cur1 = cur1->next;
            }
            if (cur2)
            {
                sum += cur2->val;
                cur2 = cur2->next;
            }
            ListNode* newnode = new ListNode(sum % 10);
            newtail->next = newnode;
            newtail = newtail->next;
            sum /= 10;
        }
        ListNode* ret = newhead->next;
        delete newhead;
        return ret;
    }
};
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
    {
        ListNode* cur1 = list1, * cur2 = list2;
        ListNode* newhead = new ListNode;
        ListNode* newtail = newhead;

        while (cur1 && cur2)
        {
            if (cur1->val < cur2->val)
            {
                newtail->next = cur1;
                newtail = newtail->next;
                cur1 = cur1->next;
            }
            else
            {
                newtail->next = cur2;
                newtail = newtail->next;
                cur2 = cur2->next;
            }
        }
        while (cur1)
        {
            newtail->next = cur1;
            newtail = newtail->next;
            cur1 = cur1->next;
        }
        while (cur2)
        {
            newtail->next = cur2;
            newtail = newtail->next;
            cur2 = cur2->next;
        }
        ListNode* ret = newhead->next;
        delete newhead;
        return ret;
    }
};
class Solution {
public:
    ListNode* detectCycle(ListNode* head)
    {
        ListNode* fast = head, * slow = head;
        ListNode* meet = nullptr;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
            {
                meet = fast;
                break;
            }
        }
        if (!meet) return nullptr;
        ListNode* cur1 = head, * cur2 = meet;
        while (cur1 != cur2)
        {
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return cur1;
    }
};
class Solution {
public:
    bool hasCycle(ListNode* head)
    {
        ListNode* fast = head, * slow = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) return true;
        }
        return false;
    }
};
class Solution {
public:
    bool isPalindrome(ListNode* head)
    {
        if (!head->next) return true;
        ListNode* fast = head, * slow = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }

        ListNode* cur = slow, * next = cur->next;
        ListNode* newhead = new ListNode;
        while (cur)
        {
            cur->next = newhead->next;
            newhead->next = cur;
            cur = next;
            if (cur) next = cur->next;
        }

        ListNode* cur1 = head, * cur2 = newhead->next;
        while (cur1 && cur2)
        {
            if (cur1->val != cur2->val) return false;
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        delete newhead;
        return true;
    }
};
class Solution {
public:
    ListNode* reverseList(ListNode* head)
    {
        if (!head || !head->next) return head;
        ListNode* tmp = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return tmp;
    }
};

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
    {
        int len1 = 0, len2 = 0;
        ListNode* cur1 = headA, * cur2 = headB;
        while (cur1)
        {
            len1++;
            cur1 = cur1->next;
        }
        while (cur2)
        {
            len2++;
            cur2 = cur2->next;
        }
        int diff = abs(len1 - len2);
        if (len1 > len2) cur1 = headA, cur2 = headB;
        else cur1 = headB, cur2 = headA;

        while (diff--) cur1 = cur1->next;
        while (cur1 && cur2)
        {
            if (cur1 == cur2) return cur1;
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return nullptr;
    }
};